def partition(A, p, q): #q超出末端位置
    x = A[p]
    i = p
    for j in range(p + 1, q): 
        if A[j] <= x:
            i += 1
            A[i], A[j] = A[j], A[i]
    A[p], A[i] = A[i], A[p]
    return i

def select(A, p, r, i):
    while r - p > 1:
        q = partition(A, p, r)
        k = q - p + 1
        if i == k: return A[q]
        elif i < k:
            r = q
        else:
            i -= k
            p = q + 1
    return A[p]

def quantilies(A, p, r, k, Q):
    if k <= 1: return
    n = len(A[p:r])
    i = k//2
    x = select(A, p, r, i*n//k)
    A[p], x = x, A[p]
    q = partition(A, p, r)
    Q.append(A[q])
    quantilies(A, p, q, k//2, Q)
    quantilies(A, q + 1, r, k - k//2, Q)
    return

if __name__=='__main__':
    Q = []
    A = [7,6,5,3,2,1,4,9,8,10]
    quantilies(A, 0, len(A), 3, Q)
    print Q
